package leetcode.code1774;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
		int n = baseCosts.length;
		int m = toppingCosts.length;
		int range = 1 << m;
		int[] dp = new int[range];
		for (int i = 0; i < range; i++) {
			int cur = 0;
			for (int j = 0; j < m; j++) {
				if ((i & (1 << j)) != 0) {
					cur += toppingCosts[j];
				}
			}
			dp[i] = cur;
		}
		int diff = Integer.MAX_VALUE;
		int ans = 0;
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < range; i++) {
				for (int j = 0; j < range; j++) {
					int t = baseCosts[k] + dp[i] + dp[j];
					int curDiff = Math.abs(t - target);
					if (curDiff < diff || (curDiff == diff && t < ans)) {
						diff = curDiff;
						ans = t;
					}
				}
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(17, this.closestCost(H.str2array3("[2,3]"), H.str2array3("[4,5,100]"), 18));
		H.compare(10, this.closestCost(H.str2array3("[1,7]"), H.str2array3("[3,4]"), 10));
		H.compare(8, this.closestCost(H.str2array3("[3,10]"), H.str2array3("[2,5]"), 9));
		H.compare(10, this.closestCost(H.str2array3("[10]"), H.str2array3("[1]"), 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
